import sortedcontainers
class Solution(object):
    def smallestRange(self, nums):
        m = len(nums)
        if m == 1:
            return [nums[0][0], nums[0][0]]
        id = [0] * m
        length = [0] * m
        for i in range(m):
            length[i] = len(nums[i])
        st = sortedcontainers.SortedList([[nums[i][0],i] for i in range(m)])
        ans = [st[0][0], st[-1][0]]
        while True:
            _, next_index = st.pop(0)
            id[next_index] += 1
            if id[next_index] < length[next_index]:
                next_val = nums[next_index][id[next_index]]
                st.add([next_val, next_index])
                new_qujian = [st[0][0], st[-1][0]]
                if new_qujian[1] - new_qujian[0] < ans[1] - ans[0]:
                    ans = new_qujian
                else:
                    if new_qujian[1] - new_qujian[0] == ans[1] - ans[0] and new_qujian[0] < ans[0]:
                        ans = new_qujian
            else:
                break
        return ans


